home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / POV-Ray 3.0.2 / src / SOURCE / OCTREE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1996-08-07  |  28.7 KB  |  1,195 lines  |  [TEXT/CWIE]
  1. /****************************************************************************
  2. *                   octree.c
  3. *
  4. *  This module contains all oct-tree functions for radiosity.
  5. *
  6. *  This file was written by Jim McElhiney.
  7. *
  8. *  from Persistence of Vision(tm) Ray Tracer
  9. *  Copyright 1996 Persistence of Vision Team
  10. *---------------------------------------------------------------------------
  11. *  NOTICE: This source code file is provided so that users may experiment
  12. *  with enhancements to POV-Ray and to port the software to platforms other
  13. *  than those supported by the POV-Ray Team.  There are strict rules under
  14. *  which you are permitted to use this file.  The rules are in the file
  15. *  named POVLEGAL.DOC which should be distributed with this file. If
  16. *  POVLEGAL.DOC is not available or for more info please contact the POV-Ray
  17. *  Team Coordinator by leaving a message in CompuServe's Graphics Developer's
  18. *  Forum.  The latest version of POV-Ray may be found there as well.
  19. *
  20. * This program is based on the popular DKB raytracer version 2.12.
  21. * DKBTrace was originally written by David K. Buck.
  22. * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
  23. *
  24. *****************************************************************************/
  25.  
  26. /************************************************************************
  27. *  Oct-tree routines.  Used by Radiosity calculation routies.
  28. *
  29. *  To understand the relationship between an ot_id (x,y,z,size) and
  30. *  a place in model space, you have to scale the integer values:
  31. *  The nominal space occupied is given as follows:
  32. *      fsize = pow(2,size-127);
  33. *      lox = (float)x *fsize; loy = (float)y * fsize; loz = (float)z * fsize;
  34. *      hix = lox + fsize;  hiy = loy + fsize;  hiz = loz + fsize;
  35. *  All elements within this node are guaranteed to stick outside of the
  36. *  nominal box by a distance of less than fsize/2 in x, y, and/or z.
  37. *  Therefore, the following box is guaranteed to contain all of the
  38. *  elements:
  39. *      minx = lox - fsize/2.;  miny = loy - fsize/2.;  minz = loz - fsize/2.;
  40. *      maxx = lox + fsize/2.;  maxy = loy + fsize/2.;  maxz = loz + fsize/2.;
  41. *  Implemented by and (c) 1994-6 Jim McElhiney, mcelhiney@acm.org  or 71201,1326
  42. *  All standard POV distribution rights granted.  All other rights reserved.
  43. *************************************************************************/
  44.  
  45. #include "frame.h"
  46. #include "vector.h"
  47. #include "povproto.h"
  48. #include "povray.h"
  49. #include "octree.h"
  50. #include "radiosit.h"
  51.  
  52.  
  53.  
  54. /*****************************************************************************
  55. * Local preprocessor defines
  56. ******************************************************************************/
  57.  
  58. #define SAFE_METHOD 1
  59. /* #define OT_DEBUG 1 */
  60.  
  61.  
  62.  
  63. /*****************************************************************************
  64. * Local typedefs
  65. ******************************************************************************/
  66.  
  67.  
  68.  
  69. /*****************************************************************************
  70. * Local variables
  71. ******************************************************************************/
  72.  
  73. #ifdef RADSTATS
  74. long ot_inscount = 0;
  75. long ot_nodecount = 0;
  76. long ot_blockcount = 0;
  77. long ot_minsize = 1000;
  78. long ot_maxsize = 0;
  79. #endif
  80.  
  81. #ifdef RADSTATS
  82. long overflows = 0;
  83. long thisloops = 0;
  84. long totloops = 0;
  85. long minloops = 1000;
  86. long maxloops = 0;
  87. #endif
  88.  
  89.  
  90.  
  91. /*****************************************************************************
  92. * Static functions
  93. ******************************************************************************/
  94.  
  95. long ot_save_node PARAMS((VECTOR point, OT_ID *node));
  96. long ot_traverse PARAMS((OT_NODE *subtree, long (*function)(OT_BLOCK *block, void * handle1), void * handle2));
  97. long ot_free_subtree PARAMS((OT_NODE *node));
  98.  
  99.  
  100.  
  101.  
  102.  
  103. /*****************************************************************************
  104. *
  105. * FUNCTION
  106. *
  107. *   ot_ins
  108. *
  109. * INPUT
  110. *   
  111. * OUTPUT
  112. *   
  113. * RETURNS
  114. *   
  115. * AUTHOUR
  116. *
  117. *   Jim McElhiney
  118. *   
  119. * DESCRIPTION
  120. *
  121. *   Called with a pointer to the root pointer, because this routine can
  122. *   create a new root block higher up.
  123. *
  124. * CHANGES
  125. *
  126. *   --- 1994 : Creation.
  127. *
  128. ******************************************************************************/
  129.  
  130. void ot_ins(root_ptr, new_block, new_id)
  131. OT_NODE **root_ptr;
  132. OT_BLOCK *new_block;    /* The data to store */
  133. OT_ID *new_id;          /* The oct-tree node id at which to store */
  134. {
  135.   long target_size, dx, dy, dz, index;
  136.   OT_NODE *temp_node, *this_node;
  137.   OT_ID temp_id;
  138.  
  139. #ifdef RADSTATS
  140.   ot_inscount++;
  141. #endif
  142.  
  143.   /* If there is no root yet, create one.  This is a first-time-through */
  144.  
  145.   if (*root_ptr == NULL)
  146.   {
  147.     *root_ptr = (OT_NODE *)POV_CALLOC(1, sizeof(OT_NODE), "octree node");
  148.  
  149. #ifdef RADSTATS
  150.     ot_nodecount = 1;
  151. #endif
  152.  
  153.     /* Might as well make it the right size for our first data block */
  154.  
  155.     (*root_ptr)->Id = *new_id;
  156.   }
  157.  
  158.   /*
  159.    * What if the thing we're inserting is bigger than the biggest node in the
  160.    * existing tree?  Add a new top to the tree till it's big enough.
  161.    */
  162.  
  163.   while ((*root_ptr)->Id.Size < new_id->Size)
  164.   {
  165.     /* root too small */
  166.  
  167.     ot_newroot(root_ptr);
  168.   }
  169.  
  170.   /*
  171.    * What if the new block is the right size, but for an area of space which
  172.    * does not overlap with the current tree?  New bigger root, until the
  173.    * areas overlap.
  174.    */
  175.  
  176.   /* Build a temp id, like a cursor to move around with */
  177.  
  178.   temp_id = *new_id;
  179.  
  180.   /* First, find the parent of our new node which is as big as root */
  181.  
  182.   while (temp_id.Size < (*root_ptr)->Id.Size)
  183.   {
  184.     ot_parent(&temp_id, &temp_id);
  185.   }
  186.  
  187.   while((temp_id.x != (*root_ptr)->Id.x) ||
  188.         (temp_id.y != (*root_ptr)->Id.y) ||
  189.         (temp_id.z != (*root_ptr)->Id.z))
  190.   {
  191.     /* while separate subtrees... */
  192.  
  193.     ot_newroot(root_ptr);       /* create bigger root */
  194.  
  195.     ot_parent(&temp_id, &temp_id);      /* and move cursor up one, too */
  196.   }
  197.  
  198.   /*
  199.    * At this point, the new node is known to fit under the current tree
  200.    * somewhere.  Go back down the tree to the right level, making new nodes
  201.    * as you go.
  202.    */
  203.  
  204.   this_node = *root_ptr;        /* start at the root */
  205.  
  206.   while (this_node->Id.Size > new_id->Size)
  207.   {
  208.     /* First, pick the node id of the child we are talking about */
  209.  
  210.     target_size = this_node->Id.Size - 1;       /* this is the size we want */
  211.  
  212.     temp_id = *new_id;  /* start with the new one */
  213.  
  214.     while (temp_id.Size < target_size)
  215.     {
  216.       ot_parent(&temp_id, &temp_id);    /* climb up till one below here */
  217.     }
  218.  
  219.     /* Now we have to pick which child number we are talking about */
  220.  
  221.     dx = (temp_id.x & 1) * 4;
  222.     dy = (temp_id.y & 1) * 2;
  223.     dz = (temp_id.z & 1);
  224.  
  225.     index = dx + dy + dz;
  226.  
  227.     if (this_node->Kids[index] == NULL)
  228.     {
  229.       /* Next level down doesn't exist yet, so create it */
  230.       temp_node = (OT_NODE *)POV_CALLOC(1, sizeof(OT_NODE), "octree node");
  231.  
  232. #ifdef RADSTATS
  233.       ot_nodecount++;
  234. #endif
  235.  
  236.       /* Fill in the data */
  237.       temp_node->Id = temp_id;
  238.  
  239.       /* Add it onto the tree */
  240.       this_node->Kids[index] = temp_node;
  241.     }
  242.  
  243.     /* Now follow it down and repeat */
  244.     this_node = this_node->Kids[index];
  245.   }
  246.  
  247.   /* Finally, we're in the right place, so insert the new value */
  248.   ot_list_insert(&(this_node->Values), new_block);
  249. }
  250.  
  251.  
  252.  
  253. /*****************************************************************************
  254. *
  255. * FUNCTION
  256. *
  257. *   ot_list_insert
  258. *
  259. * INPUT
  260. *   
  261. * OUTPUT
  262. *   
  263. * RETURNS
  264. *   
  265. * AUTHOUR
  266. *
  267. *   Jim McElhiney
  268. *   
  269. * DESCRIPTION
  270. *
  271. *   -
  272. *
  273. * CHANGES
  274. *
  275. *   --- 1994 : Creation.
  276. *
  277. ******************************************************************************/
  278.  
  279. void ot_list_insert(list_head, new_block)
  280. OT_BLOCK **list_head;
  281. OT_BLOCK *new_block;
  282. {
  283.   new_block->next = *list_head; /* copy addr of old first block */
  284.  
  285.   *list_head = new_block;
  286. }
  287.  
  288.  
  289.  
  290. /*****************************************************************************
  291. *
  292. * FUNCTION
  293. *
  294. *   ot_newroot
  295. *
  296. * INPUT
  297. *   
  298. * OUTPUT
  299. *   
  300. * RETURNS
  301. *   
  302. * AUTHOUR
  303. *
  304. *   Jim McElhiney
  305. *   
  306. * DESCRIPTION
  307. *
  308. *   Modify a tree so that it has a bigger root, owning the old root passed in.
  309. *   Note that this function is called with a POINTER TO the root pointer,
  310. *   since the root pointer will be changed.
  311. *
  312. * CHANGES
  313. *
  314. *   --- 1994 : Creation.
  315. *
  316. ******************************************************************************/
  317.  
  318. void ot_newroot(root_ptr)
  319. OT_NODE **root_ptr;
  320. {
  321.   OT_NODE *newroot;
  322.   long dx, dy, dz, index;
  323.  
  324.   newroot = (OT_NODE *)POV_CALLOC(1, sizeof(OT_NODE), "octree node");
  325.  
  326. #ifdef RADSTATS
  327.   ot_nodecount++;
  328. #endif
  329.   ot_parent(&newroot->Id, &((*root_ptr)->Id));  /* sets the x/y/z/size id */
  330.  
  331.   /*
  332.    * Function:  decide which child of the new root the old root is. Theory:
  333.    * x,y,z values are measured in block sizes, and are a factor of 2 smaller
  334.    * at each level higher.  The parent of both (3,4,5,k) and (2,5,4,k) is
  335.    * (1,2,2,k+1), so the oddness of the child's ordinates determines which
  336.    * child it is, and hence the value of the index into the parent's array of
  337.    * children.  First half of array (4 entries) is kids with low/even x;
  338.    * First half of those is kids with low/even y (2 entries), and the very
  339.    * first entry is the one with low/even everything.
  340.    */
  341.   dx = ((*root_ptr)->Id.x & 1) * 4;
  342.   dy = ((*root_ptr)->Id.y & 1) * 2;
  343.   dz = ((*root_ptr)->Id.z & 1);
  344.   index = dx + dy + dz;
  345.   newroot->Kids[index] = *root_ptr;
  346.   *root_ptr = newroot;
  347. }
  348.  
  349.  
  350.  
  351. /*****************************************************************************
  352. *
  353. * FUNCTION
  354. *
  355. *   ot_dist_traverse
  356. *
  357. * INPUT
  358. *   
  359. * OUTPUT
  360. *   
  361. * RETURNS
  362. *   
  363. * AUTHOUR
  364. *
  365. *   Jim McElhiney
  366. *   
  367. * DESCRIPTION
  368. *
  369. *   Call "function(&node, handle)" for every node which is less than a node
  370. *   width from the test point. Post traverse = small stuff first = the kids
  371. *   before this node. "function(*node, handle)" must return true/false on
  372. *   whether or not to continue with further processing.  Returns 0 if
  373. *   execution was halted this way, 1 otherwise;
  374. *
  375. * CHANGES
  376. *
  377. *   --- 1994 : Creation.
  378. *
  379. ******************************************************************************/
  380.  
  381. long ot_dist_traverse(subtree, point, bounce_depth, function, handle)
  382. OT_NODE *subtree;
  383. VECTOR point;
  384. int bounce_depth;               /* only those nodes with this recur depth */
  385. long (*function) PARAMS((OT_BLOCK * bl, void *handle1));
  386. void *handle;
  387. {
  388. #ifdef RADSTATS
  389.   extern long ot_seenodecount, ot_seeblockcount;
  390.  
  391. #endif
  392.   long i, oksofar;
  393.   OT_NODE *this_node;
  394.   OT_BLOCK *this_block;
  395.  
  396. #ifdef RADSTATS
  397.   ot_seenodecount++;
  398. #endif
  399.  
  400.   /* First, recurse to the child nodes */
  401.   oksofar = 1;
  402.   for (i = 0; i < 8 && oksofar; i++)
  403.   {     /* for each potential kid */
  404.     this_node = subtree->Kids[i];
  405.     if (this_node != NULL)
  406.     {   /* ...which exists */
  407.       if (ot_point_in_node(point, &this_node->Id))
  408.       { /* ...and in range */
  409.         oksofar = ot_dist_traverse(this_node, point, bounce_depth,
  410.                                    function, handle);
  411.       }
  412.     }
  413.   }
  414.  
  415.   /*
  416.    * Now, call the specified routine for each data block hung off this tree
  417.    * node
  418.    */
  419.  
  420.   /* if ( ot_point_in_node(point, &subtree->Id) ) { */
  421.   {
  422.     this_block = subtree->Values;
  423.     while (oksofar && (this_block != NULL))
  424.     {
  425. #ifdef RADSTATS
  426.       if (subtree->Id.Size < 100 || subtree->Id.Size > 140 )
  427.       {
  428.         Debug_Info("bounds error, unreasonable size %d\n", subtree->Id.Size);
  429.       }
  430.       ot_seeblockcount++;
  431. #endif
  432.       if ((int)this_block->Bounce_Depth == bounce_depth)
  433.       {
  434.         oksofar = (*function) (this_block, handle);
  435.       }
  436.       this_block = this_block->next;
  437.     }
  438.   }
  439.  
  440.   return oksofar;
  441. }
  442.  
  443.  
  444. /*****************************************************************************
  445. *
  446. * FUNCTION
  447. *
  448. *   ot_traverse - call a function for every block in the tree.
  449. *
  450. * INPUT
  451. *   
  452. * OUTPUT
  453. *   
  454. * RETURNS
  455. *   
  456. * AUTHOUR
  457. *
  458. *   Jim McElhiney
  459. *   
  460. * DESCRIPTION
  461. *
  462. * Call "function(&block, handle)" for every block hanging off every node.
  463. *   Post traverse = small stuff first = the kids before this node.
  464. *   "function(*node, handle)" must return true/false on whether or not to
  465. *   Continue with further processing.  Returns 0 if execution
  466. *   was halted this way, 1 otherwise;
  467. *
  468. * CHANGES
  469. *
  470. *   --- Jan 1996 : Creation.
  471. *
  472. ******************************************************************************/
  473. long
  474. ot_traverse(subtree, function, handle)
  475. /* Call "function(&block, handle)" for every block hanging off every node.
  476.    Post traverse = small stuff first = the kids before this node.
  477.    "function(*node, handle)" must return true/false on whether or not to
  478.    Continue with further processing.  Returns 0 if execution
  479.    was halted this way, 1 otherwise;
  480. */
  481. OT_NODE *subtree;
  482. long (*function)(OT_BLOCK * bl, void * handle1);
  483. void *handle;
  484. {
  485.   long i, oksofar;
  486.   OT_NODE *this_node;
  487.   OT_BLOCK *this_block;
  488.  
  489.  
  490.   /* First, recurse to the child nodes */
  491.   oksofar = 1;
  492.   if (subtree!=NULL)
  493.   {
  494.     
  495.     for (i=0; i<8 && oksofar; i++ )     /* for each potential kid */
  496.     {
  497.       this_node = subtree->Kids[i];
  498.       if ( this_node != NULL )          /* ...which exists */
  499.       {
  500.         oksofar = ot_traverse(this_node, function, handle);
  501.       }
  502.     }
  503.  
  504.     /* Now, call the specified routine for each data block hung off
  505.        this tree node */
  506.     this_block = subtree->Values;
  507.     while ( oksofar  &&  (this_block != NULL) )
  508.     {
  509.       oksofar = (*function)(this_block, handle);
  510.       this_block = this_block->next;
  511.     }
  512.   }
  513.  
  514.   return oksofar;
  515. }
  516.  
  517.  
  518.  
  519. /*****************************************************************************
  520. *
  521. * FUNCTION
  522. *
  523. *   ot_point_in_node
  524. *
  525. * INPUT
  526. *   
  527. * OUTPUT
  528. *   
  529. * RETURNS
  530. *   
  531. * AUTHOUR
  532. *
  533. *   Jim McElhiney
  534. *   
  535. * DESCRIPTION
  536. *
  537. *   Returns true if the specified point is inside the max extent of the node
  538. *   with the specified ID.
  539. *
  540. * CHANGES
  541. *
  542. *   --- 1994 : Creation.
  543. *
  544. ******************************************************************************/
  545.  
  546. long ot_point_in_node(point, id)
  547. VECTOR point;
  548. OT_ID *id;
  549. {
  550.   DBL sized, minx, miny, minz, lox, loy, loz, hix, hiy, hiz;
  551.  
  552.   union
  553.   {
  554.     float f;
  555.     long l;
  556.   }
  557.   size;                         /* MUST be float, NOT DBL */
  558.  
  559.   size.l = id->Size << 23;
  560.   sized = (DBL) size.f;
  561.   minx = (DBL) id->x * sized - OT_BIAS;
  562.   miny = (DBL) id->y * sized - OT_BIAS;
  563.   minz = (DBL) id->z * sized - OT_BIAS;
  564.  
  565.   lox = minx - sized * .5;
  566.   hix = minx + sized * 1.5;
  567.   loy = miny - sized * .5;
  568.   hiy = miny + sized * 1.5;
  569.   loz = minz - sized * .5;
  570.   hiz = minz + sized * 1.5;
  571.  
  572.   return(point[X] >= lox && point[X] < hix &&
  573.          point[Y] >= loy && point[Y] < hiy &&
  574.          point[Z] >= loz && point[Z] < hiz);
  575. }
  576.  
  577.  
  578.  
  579. /*****************************************************************************
  580. *
  581. * FUNCTION
  582. *
  583. *   ot_index_sphere
  584. *
  585. * INPUT
  586. *   
  587. * OUTPUT
  588. *   
  589. * RETURNS
  590. *   
  591. * AUTHOUR
  592. *
  593. *   Jim McElhiney
  594. *   
  595. * DESCRIPTION
  596. *
  597. *   Return the oct-tree index for an object with the specified bounding
  598. *   sphere. This is the smallest box in the tree that this object fits in with
  599. *   a maximum 50% hand-over in any (or all) directions. For example, an object
  600. *   at (.49, .49, 49) of radius 1 fits in the box (0,0,0) size 127 (length 1).
  601. *
  602. * CHANGES
  603. *
  604. *   --- 1994 : Creation.
  605. *
  606. ******************************************************************************/
  607.  
  608. void ot_index_sphere(point, radius, id)
  609. VECTOR point;
  610. DBL radius;
  611. OT_ID *id;
  612. {
  613.   VECTOR min_point, max_point;
  614.  
  615.   min_point[X] = point[X] - radius;
  616.   min_point[Y] = point[Y] - radius;
  617.   min_point[Z] = point[Z] - radius;
  618.   max_point[X] = point[X] + radius;
  619.   max_point[Y] = point[Y] + radius;
  620.   max_point[Z] = point[Z] + radius;
  621.  
  622.   ot_index_box(min_point, max_point, id);
  623.  
  624. #ifdef RADSTATS
  625.   if (id->Size < ot_minsize)
  626.   {
  627.     ot_minsize = id->Size;
  628.   }
  629.   if (id->Size > ot_maxsize)
  630.   {
  631.     ot_maxsize = id->Size;
  632.   }
  633. #endif
  634. }
  635.  
  636.  
  637.  
  638.  
  639. /*****************************************************************************
  640. *
  641. * FUNCTION
  642. *
  643. *   ot_index_box
  644. *
  645. * INPUT
  646. *   
  647. * OUTPUT
  648. *   
  649. * RETURNS
  650. *   
  651. * AUTHOUR
  652. *
  653. *   Jim McElhiney
  654. *   
  655. * DESCRIPTION
  656. *
  657. *   Return the oct-tree index for an object with the specified bounding box.
  658. *   near_point is lox, loy, loz; far_point is hix, hiy, hiz. This is the
  659. *   smallest box in the tree that this object fits in with a maximum 50%
  660. *   hang-over in any (or all) directions. For example, an object with extent
  661. *   (-.49, -.49, -49) to (1.49, 1.49, 1.49) is the largest that fits in the
  662. *   box (0,0,0) with size 127 (length 1).
  663. *
  664. *   PORTABILITY WARNING:  this function REQUIRES IEEE single precision floating
  665. *   point format to work.  This is true of most common systems except VAXen,
  666. *   Crays, and Alpha AXP in VAX compatibility mode.  Local "float" variables
  667. *   can NOT be made double precision "double" or "DBL".
  668. *
  669. * CHANGES
  670. *
  671. *   --- 1994 : Creation.
  672. *
  673. ******************************************************************************/
  674.  
  675. void ot_index_box(min_point, max_point, id)
  676. VECTOR min_point;
  677. VECTOR max_point;
  678. OT_ID *id;
  679. {
  680.   long done, idx, idy, idz;
  681.   float dx, dy, dz, maxdel;     /* MUST BE "float" NOT "DBL" */
  682.   DBL bsized, maxord;
  683.   union
  684.   {
  685.     float f;
  686.     long l;
  687.   }
  688.   convert;
  689.   OT_ID base_id, test_id;
  690.  
  691.   dx = (float) (max_point[X] - min_point[X]);
  692.   dy = (float) (max_point[Y] - min_point[Y]);
  693.   dz = (float) (max_point[Z] - min_point[Z]);
  694.   maxdel = MAX3(dx, dy, dz);
  695.  
  696.   /*
  697.    * This hex operation does a floor to next lower power of 2, by clearing
  698.    * all of the mantissa bits.  Works only on IEEE single precision floats
  699.    */
  700.   convert.f = maxdel;
  701.   convert.l &= 0xff800000;
  702.   bsized = (DBL) convert.f;
  703.  
  704. #ifdef SAFE_METHOD
  705.  
  706.   /*
  707.    * This block checks for the case where the node id would cause integer
  708.    * overflow, since it is a small buffer far away
  709.    */
  710.   maxord = MAX3(fabs(min_point[X]), fabs(min_point[Y]), fabs(min_point[Z]));
  711.   maxord += OT_BIAS;
  712.   while (maxord / bsized > 1000000000.)
  713.   {
  714. #ifdef RADSTATS
  715.     overflows++;
  716. #endif
  717.     bsized *= 2.;
  718.   }
  719. #endif
  720.  
  721.   /* calculate the smallest possible node that the item might fit into */
  722.   base_id.x = (long) floor((min_point[X] + OT_BIAS) / bsized);
  723.   base_id.y = (long) floor((min_point[Y] + OT_BIAS) / bsized);
  724.   base_id.z = (long) floor((min_point[Z] + OT_BIAS) / bsized);
  725.  
  726.   /*
  727.    * This magic hex operation extracts the exponent, which gives us an
  728.    * integer number suitable for labelling a range of a power of 2.  In IEEE
  729.    * format, value = pow(2,exponent-127). Therefore, if our index is, say,
  730.    * 129, then the item has a maximum extent of (2 to the (129-127)), or
  731.    * about 4 space units.
  732.    */
  733.   convert.f = (float) bsized;
  734.   base_id.Size = (convert.l & 0x7f800000) >> 23;
  735.  
  736.   /* Now increase the node size until it fits for sure */
  737. #ifdef RADSTATS
  738.   thisloops = 0;
  739. #endif
  740.   done = 0;
  741.   while (!done)
  742.   {
  743.     test_id.Size = base_id.Size;
  744.     for (idx = 0; idx < 2 && !done; idx++)
  745.     {
  746.       for (idy = 0; idy < 2 && !done; idy++)
  747.       {
  748.         for (idz = 0; idz < 2 && !done; idz++)
  749.         {
  750.           test_id.x = base_id.x + idx;
  751.           test_id.y = base_id.y + idy;
  752.           test_id.z = base_id.z + idz;
  753.           if (ot_point_in_node(min_point, &test_id) &&
  754.               ot_point_in_node(max_point, &test_id))
  755.           {
  756.             done = 1;
  757.           }
  758.         }
  759.       }
  760.     }
  761.  
  762.     /*
  763.      * Debug_Info("looping %d,%d,%d,%d  min=%d, max=%d\n", test_id.x, test_id.y,
  764.      * test_id.z, test_id.Size, ot_point_in_node(min_point, &test_id),
  765.      * ot_point_in_node(max_point, &test_id));
  766.      */
  767.     ot_parent(&base_id, &base_id);
  768. #ifdef RADSTATS
  769.     totloops++;
  770.     thisloops++;
  771. #endif
  772.   }
  773. #ifdef RADSTATS
  774.   if (thisloops < minloops)
  775.     minloops = thisloops;
  776.   if (thisloops > maxloops)
  777.     maxloops = thisloops;
  778. #endif
  779.   *id = test_id;
  780.  
  781. #ifdef OT_DEBUG
  782.   if (id->Size > 139)
  783.   {
  784.     Debug_Info("unusually large id, maxdel=%.4f, bsized=%.4f, isize=%d\n",
  785.            maxdel, bsized, id->Size);
  786.   }
  787. #endif
  788. }
  789.  
  790.  
  791.  
  792. /*****************************************************************************
  793. *
  794. * FUNCTION
  795. *
  796. *   ot_parent
  797. *
  798. * INPUT
  799. *   
  800. * OUTPUT
  801. *   
  802. * RETURNS
  803. *   
  804. * AUTHOUR
  805. *
  806. *   Jim McElhiney
  807. *   
  808. * DESCRIPTION
  809. *
  810. *   Set the x/y/z/size block ID info of dad = the parent ID of kid
  811. *
  812. * CHANGES
  813. *
  814. *   --- 1994 : Creation.
  815. *
  816. ******************************************************************************/
  817.  
  818. void ot_parent(dad_id, kid_id)
  819. OT_ID *dad_id, *kid_id;
  820. {
  821.   dad_id->Size = kid_id->Size + 1;
  822.   dad_id->x = (kid_id->x > 0) ? (kid_id->x >> 1) : (kid_id->x - 1) / 2;
  823.   dad_id->y = (kid_id->y > 0) ? (kid_id->y >> 1) : (kid_id->y - 1) / 2;
  824.   dad_id->z = (kid_id->z > 0) ? (kid_id->z >> 1) : (kid_id->z - 1) / 2;
  825. }
  826.  
  827.  
  828.  
  829. /*****************************************************************************
  830. *
  831. * FUNCTION
  832. *
  833. *   ot_save_tree
  834. *
  835. * INPUT
  836. *   
  837. * OUTPUT
  838. *   
  839. * RETURNS 1 for success, 0 for failure.
  840. *   
  841. * AUTHOUR
  842. *
  843. *   Jim McElhiney
  844. *   
  845. * DESCRIPTION
  846. *
  847. *   Given the root pointer of the in-memory cache tree, and a file descriptor
  848. *   of a file you want to write to, write the whole tree to that file.
  849. *
  850. * CHANGES
  851. *
  852. *   Jan 1996 : Creation by JDM.
  853. *
  854. * TO DO
  855. *
  856. *  Code must be written which turns Radiosity_File_*  flags on and off.
  857. *  These flags should be in the opts structure.
  858. *
  859. ******************************************************************************/
  860. long
  861. ot_save_tree(root, fd)
  862. OT_NODE *root;
  863. FILE *fd;
  864. {
  865.   long retval = 0;
  866.  
  867.   if ( fd != NULL ) {
  868.     retval = ot_traverse(root, &ot_write_block, (void *)fd);
  869.   }
  870.   else
  871.   {
  872.     Warning(0.0, "bad radiosity cache file handle\n");
  873.   }
  874.  
  875.   return retval;
  876. }
  877.  
  878.  
  879.  
  880. /*****************************************************************************
  881. *
  882. * FUNCTION
  883. *
  884. *   ot_write_block
  885. *
  886. * INPUT
  887. *   
  888. * OUTPUT
  889. *   
  890. * RETURNS
  891. *   
  892. * AUTHOUR
  893. *
  894. *   Jim McElhiney
  895. *   
  896. * DESCRIPTION
  897. *
  898. *   Write one block (not a node) from the memory cache to the cache file.
  899. *
  900. * CHANGES
  901. *
  902. *   --- Jan 1996 : Creation.
  903. *
  904. ******************************************************************************/
  905. long
  906. ot_write_block(bl, fd)
  907. OT_BLOCK *bl;
  908. void *fd;        /* must be passed as void * for compatibility */
  909. {
  910.  
  911.   if ( bl->Bounce_Depth == 1 )
  912.   {
  913.     fprintf((FILE *)fd, "C%ld\t%g\t%g\t%g\t%02x%02x%02x\t%.4f\t%.4f\t%.4f\t%g\t%g\t%02x%02x%02x\n",
  914.       (long)bl->Bounce_Depth,
  915.  
  916.       bl->Point[X], bl->Point[Y], bl->Point[Z],
  917.       (long)((bl->S_Normal[X]+1.)*.5*254.+.499999),
  918.       (long)((bl->S_Normal[Y]+1.)*.5*254.+.499999),
  919.       (long)((bl->S_Normal[Z]+1.)*.5*254.+.499999),
  920.  
  921.       bl->Illuminance[X], bl->Illuminance[Y], bl->Illuminance[Z],
  922.       bl->Harmonic_Mean_Distance,
  923.       
  924.       bl->Nearest_Distance,
  925.       (long)((bl->To_Nearest_Surface[X]+1.)*.5*254.+.499999),
  926.       (long)((bl->To_Nearest_Surface[Y]+1.)*.5*254.+.499999),
  927.       (long)((bl->To_Nearest_Surface[Z]+1.)*.5*254.+.499999)
  928.     );
  929.   }
  930.   return 1;
  931. }
  932.  
  933.  
  934. /*****************************************************************************
  935. *
  936. * FUNCTION
  937. *
  938. *   ot_free_tree() - get rid of the entire in-memory radiosity cache tree,
  939. *   and zero the pointer to its root.
  940. *
  941. * INPUT - pointer to the tree root pointer.
  942. *   
  943. * RETURNS - success 1, failure 0
  944. *   
  945. * AUTHOUR
  946. *
  947. *   Jim McElhiney
  948. *   
  949. * DESCRIPTION
  950. *
  951. *   Free a complete radiosity cache tree, and all of its nodes and blocks.
  952. *   NOTE parameter is a pointer to the tree pointer...tree pointer will get zeroed.
  953. *   Example call:
  954. *      ot_free_tree(&ot_root);
  955. *   Returns 1 for success, 0 for failure.
  956. *
  957. * CHANGES
  958. *
  959. *   --- Jan 1996 : Creation.
  960. *
  961. ******************************************************************************/
  962. long
  963. ot_free_tree(ppRoot)
  964. /* Free a complete radiosity cache tree, and all of its nodes and blocks.
  965.    Note parameter is a pointer to the tree pointer...tree pointer will get zeroed.
  966.    Example call:
  967.       ot_free_tree(&ot_root);
  968.    Returns 1 for success, 0 for failure.
  969. */
  970. OT_NODE **ppRoot;
  971. {
  972.   long all_ok;
  973.  
  974.   all_ok = ot_free_subtree(*ppRoot);
  975.   *ppRoot = NULL;
  976.  
  977.   return all_ok;
  978. }
  979.  
  980.  
  981. /*****************************************************************************
  982. *
  983. * FUNCTION
  984. *
  985. *   ot_free_subtree - free every node from this node downwards, and all blocks
  986. *   hanging off those nodes, and then free the node which was passed.
  987. *
  988. * INPUT
  989. *   
  990. * OUTPUT
  991. *   
  992. * RETURNS
  993. *   
  994. * AUTHOUR
  995. *
  996. *   Jim McElhiney
  997. *   
  998. * DESCRIPTION
  999. *
  1000. *   Set the x/y/z/size block ID info of dad = the parent ID of kid
  1001. *
  1002. * CHANGES
  1003. *
  1004. *   --- Jan 1996 : Creation.
  1005. *
  1006. ******************************************************************************/
  1007. long
  1008. ot_free_subtree(subtree)
  1009. /* Free this subtree.  That is, free all of its daughters, then 
  1010.    free all of the blocks hanging off this node, then free this node itself.
  1011.  
  1012.    Returns 0 if problems were encountered anywhere in the tree.
  1013.    Currently, this code assumes success.  If called with an invalid tree pointer,
  1014.    it would probably crash with a memory protection error.
  1015. */
  1016. OT_NODE *subtree;
  1017. {
  1018.   long i, oksofar;
  1019.   OT_NODE *this_node;
  1020.   OT_BLOCK *this_block, *next_block;
  1021.  
  1022.   /* First, recurse to the child nodes */
  1023.   oksofar = 1;
  1024.   for (i=0; i<8 && oksofar; i++ )   /* for each potential kid */
  1025.   {
  1026.     this_node = subtree->Kids[i];
  1027.     if ( this_node != NULL ) {      /* ...which exists */
  1028.       oksofar &= ot_free_subtree(this_node);
  1029.     }
  1030.   }
  1031.  
  1032.   /* Now, free each block hanging off this node. */
  1033.   this_block = subtree->Values;
  1034.   while ( this_block != NULL )
  1035.   {
  1036.     next_block = this_block->next;
  1037.     POV_FREE(this_block);
  1038.     this_block = next_block;
  1039.   }
  1040.  
  1041.   /* Finally, free this block itself */
  1042.   POV_FREE(subtree);
  1043.  
  1044.   return oksofar;
  1045. }
  1046.  
  1047.  
  1048. /*****************************************************************************
  1049. *
  1050. * FUNCTION
  1051. *
  1052. *   ot_read_file
  1053. *
  1054. * INPUT
  1055. *   file descriptor handle of file (already opened) to read into memory.
  1056. *   
  1057. * OUTPUT
  1058. *   
  1059. * RETURNS - Success 1 / failure 0
  1060. *   
  1061. * AUTHOUR
  1062. *
  1063. *   Jim McElhiney
  1064. *   
  1065. * DESCRIPTION
  1066. *
  1067. *   Read in a radiosity cache file, building a tree from its values.
  1068. *   If there is an existing tree, these values are added to it.
  1069. *
  1070. * CHANGES
  1071. *
  1072. *   --- Jan 1996 : Creation.
  1073. *
  1074. ******************************************************************************/
  1075. long
  1076. ot_read_file(fd)
  1077. /* Read in a radiosity cache file, building a tree from its values.
  1078.    If there is an existing tree, these values are added to it.
  1079. */
  1080. FILE *fd;
  1081. {
  1082.   long retval, line_num, tempdepth, tx, ty, tz, goodreads;
  1083.   int count, goodparse, readret;
  1084.   DBL brightness;
  1085.   OT_BLOCK bl, *new_block;
  1086.   OT_ID id;
  1087.   char normal_string[30], to_nearest_string[30], line[101];
  1088.  
  1089.   memset(&bl, 0, sizeof(OT_BLOCK));
  1090.  
  1091.   if ( fd != NULL )
  1092.   {
  1093.     line_num = 0;
  1094.  
  1095.     Make_Colour(Radiosity_Gather_Total, 0., 0., 0.);
  1096.     Radiosity_Gather_Total_Count = 0;
  1097.  
  1098.     goodparse = 1;
  1099.     goodreads = 0;
  1100.  
  1101.     while ( ((readret = fscanf(fd, "%99[^\n]\n", line)) == 1) && goodparse )
  1102.     {
  1103.       switch ( line[0] )
  1104.       {
  1105.         case 'B':    /* the file contains the old radiosity_brightness value */
  1106.         {
  1107.           if ( sscanf(line, "B%lf\n", &brightness) == 1 )
  1108.           {
  1109.             opts.Radiosity_Brightness = brightness;
  1110.           }
  1111.           break;
  1112.         }
  1113.         case 'P':    /* the file made it to the point that the Preview was done */
  1114.         {
  1115.           opts.Radiosity_Preview_Done = 1;
  1116.           break;
  1117.         }    
  1118.         case 'C':
  1119.         {
  1120.           count = sscanf(line, "C%d %lf %lf %lf %s %f %f %f %f %f %s\n",
  1121.                      &tempdepth,      /* since you can't scan a short */
  1122.                      &bl.Point[X], &bl.Point[Y], &bl.Point[Z],
  1123.                      normal_string,
  1124.                      &bl.Illuminance[X], &bl.Illuminance[Y], &bl.Illuminance[Z],
  1125.                      &bl.Harmonic_Mean_Distance,
  1126.                      &bl.Nearest_Distance, to_nearest_string );
  1127.           if ( count == 11 )
  1128.           {
  1129.             bl.Bounce_Depth = (short)tempdepth;
  1130.  
  1131.             /* normals aren't very critical for direction precision, so they are packed */
  1132.             sscanf(normal_string, "%02lx%02lx%02lx", &tx, &ty, &tz);
  1133.             bl.S_Normal[X] = ((double)tx * (1./ 254.))*2.-1.;
  1134.             bl.S_Normal[Y] = ((double)ty * (1./ 254.))*2.-1.;
  1135.             bl.S_Normal[Z] = ((double)tz * (1./ 254.))*2.-1.;
  1136.             VNormalizeEq(bl.S_Normal);
  1137.  
  1138.             sscanf(to_nearest_string, "%02lx%02lx%02lx", &tx, &ty, &tz);
  1139.             bl.To_Nearest_Surface[X] = ((double)tx * (1./ 254.))*2.-1.;
  1140.             bl.To_Nearest_Surface[Y] = ((double)ty * (1./ 254.))*2.-1.;
  1141.             bl.To_Nearest_Surface[Z] = ((double)tz * (1./ 254.))*2.-1.;
  1142.             VNormalizeEq(bl.To_Nearest_Surface);
  1143.  
  1144.             line_num++;
  1145.  
  1146.             new_block = (OT_BLOCK *)POV_MALLOC(sizeof (OT_BLOCK), "octree node from file");
  1147.             if ( new_block != NULL )
  1148.             {
  1149.               memcpy(new_block, &bl, sizeof (OT_BLOCK));
  1150.  
  1151.               ot_index_sphere(bl.Point, bl.Harmonic_Mean_Distance * opts.Radiosity_Error_Bound, &id);
  1152.               ot_ins(&ot_root, new_block, &id);
  1153.               goodreads++;
  1154.             }
  1155.             else
  1156.             {
  1157.               goodparse = 0;    /* allocation error, better stop now */
  1158.             }
  1159.           }
  1160.           break;
  1161.         }
  1162.  
  1163.         default:
  1164.         {
  1165.           /* wrong leading character on line, just try again on next line */
  1166.         }
  1167.  
  1168.       }   /* end switch */
  1169.     }     /* end while-reading loop */
  1170.  
  1171.     if ( (readret != EOF)  ||  !goodparse ) {
  1172.       Status_Info("\nError processing the radiosity cache file at line %ld", (long)line);
  1173.       retval = 0;
  1174.     }
  1175.     else
  1176.     {
  1177.       if ( goodreads > 0 )
  1178.       {
  1179.         Status_Info("\nReloaded %ld values from radiosity cache file.", goodreads);
  1180.       }
  1181.       else
  1182.       {
  1183.         Status_Info("\nUnable to read any values from the radiosity cache file.");
  1184.       }
  1185.       retval = 1;
  1186.     }
  1187.   }
  1188.   else
  1189.   {
  1190.     retval = 0;
  1191.   }
  1192.  
  1193.   return retval;
  1194. }
  1195.